/**
 * @author : xwj
 * @date : 2021/9/13 22:53
 * @description : 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * @class : test21
 **/

public class test21 {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //1. 0 ms	37.6 MB
    // 如果l1,l2为空，直接返回l2,l1。设置一个临时结点，用来存放初始节点，防止后续找不到头结点
    // 用一个节点来存放l1的前一个节点，便于插入。
    // 将l2中的数插入到l1中
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode head = new ListNode(0, l1);
        ListNode pre = head;
        while (l1 != null && l2 != null) {
            if (l1.val >= l2.val) {
                pre.next = l2;
                l2 = l2.next;
                pre = pre.next;
                pre.next = l1;
            } else {
                pre = pre.next;
                l1 = l1.next;
            }
        }
        if (l2 != null) {
            pre.next = l2;
        }
        return head.next;
    }

    //新创建一个节点，将l1,l2一次比较遍历，大的放进去，直接返回该节点即可
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(0);
        ListNode pre = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                pre.next = l1;
                l1 = l1.next;
            } else {
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }

        pre.next = l1 == null ? l2 : l1;

        return prehead.next;
    }

    public static void main(String[] args) {
        ListNode tail = new ListNode(3);
        ListNode tmp = new ListNode(2, tail);
        ListNode head = new ListNode(1, tmp);

        ListNode tail1 = new ListNode(3);
        ListNode tmp1 = new ListNode(2, tail1);
        ListNode head1 = new ListNode(1, tmp1);

        ListNode l = mergeTwoLists2(head1, head);
        while (head != null) {
            System.out.println(head.val);
            head = head.next;
        }
    }

}
